#include "leetcode_util.h"

int helper1(vector<char>& A, int s1, vector<char>& B, int s2, int count) {
    if (s1 == A.size()) return count + B.size() - s2;
    if (s2 == B.size()) return count + A.size() - s1;

    if (A[s1] == B[s2]) {
        // a|xxxxx & a|yyyyy: the supersequence should be a|xxxxxyyyyy
        return helper1(A, s1+1, B, s2+1, count+1);
    } else {
        // a|xxxxx & b|yyyyy: min(a|xxxxxbyyyyy, b|yyyyyaxxxxx)
        return min(helper1(A, s1+1, B, s2, count+1), helper1(A, s1, B, s2+1, count+1));
    }
}

int solution1(vector<char>& A, vector<char>& B) {
    return helper1(A, 0, B, 0, 0);
}

int solution2(vector<char>& A, vector<char>& B) {
    if (A.empty()) return B.size();
    if (B.empty()) return A.size();

    int m = A.size();
    int n = B.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, m+n));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i-1] == B[j-1]) {
                dp[i][j] = dp[i-1][j-1] - 1;
            } else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

void showVector(vector<int>& A) {
    vector<int>::iterator itr = A.begin();
    for(; itr != A.end();) {
        printf("%d", *itr);
        if (++itr != A.end()) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
}

void testVector(int argc, char *argv[]) {
    string s;
    for (int i = 1; i < argc; i++) {
        s = string(argv[i]);
        vector<int> v = stringToVector(s);
        // test function

        // cout << numberOfArithmeticSlices(v) << endl;
    }
}

int main(int argc, char *argv[]) {
    string s = "abcbdabcabfga bdcababcaebgf";
    //string s = "ace acf";
    stringstream ss(s);
    vector<string> s0;
    string token;
    while (getline(ss, token, ' ')) {
        s0.push_back(token);
    }
    vector<char> a(s0[0].begin(), s0[0].end());
    vector<char> b(s0[1].begin(), s0[1].end());

    int result;
    int N = 10000;
    clock_t c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution1(a, b);
    }
    cout << "solution1: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution2(a, b);
    }
    cout << "solution2: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    /*
    c_start = clock();
    for (int i = 0; i < N; ++i) {
        result = solution3(a, b);
    }
    cout << "solution3: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    */
}

